package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202410;

import java.util.Arrays;

public class leetcode20241017 {

    public int numberOfPermuations(int n,int[][] requirements){
        int[] req=new int[n];
        Arrays.fill(req,-1);
        req[0]=0;
        int m=0;
        for(int[] p : requirements){
            req[p[0]]=p[1];
            m=Math.max(m,p[1]);
        }
        if(req[0]>0){
            return 0;
        }

        // 回溯算法
        int[][] memo=new int[n][m+1];
        for(int[] row : memo){
            Arrays.fill(row,-1);// -1表示没有计算过
        }
        return dfs(n-1,req[n-1],req,memo);
    }

    private int dfs(int i,int j,int[] req,int[][] memo){
        if(i==0){
            return 1;
        }
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
        int res=0;
        int r=req[i-1];
        if(r>=0){
            if(j>=r && j-i<=r){
                res=dfs(i-1,r,req,memo);
            }
        }else{
            for(int k=0;k<=Math.min(i,j);k++){
                res=(res+dfs(i-1,j-k,req,memo))%1000000007;
            }
        }
        return memo[i][j]=res;// 记忆化
    }
}
